package com.fanshuai.algorithms.dynamic;

/**
 * 假设有一个特殊的键盘包含4个键：
 * A: 敲击字母A
 * Ctrl-A: 选中屏幕
 * Ctrl-C: 复制
 * Ctrl-V: 粘贴
 * 可以按键N次，屏幕上最多显示几个A？
 */
public class KeyBoard {

    /**
     * 最优按键序列一定只有两种情况：
     要么一直按 A：A,A,...A（当 N 比较小时）。
     要么是这么一个形式：A,A,...C-A,C-C,C-V,C-V,...C-V（当 N 比较大时）。

     定义：dp[i] 表示 i 次操作后最多能显示多少个 A
     for (int i = 0; i <= N; i++)
        dp[i] = max(
            这次按 A 键，
            这次按 C-V
        )

     用一个变量 j 作为若干 C-V 的起点的前一次C-C，C-V操作次数为i - j。j-1, j-2操作为A，C-A
     * @param n
     * @return
     */
    public static int keyBoard(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1; //按A键

            for (int j = 3; j <= i; j++) {
                //dp[j - 2]为C-A之前的A个数，dp[j - 2] * (i - j)为复制了(i - j)
                dp[i] = Math.max(dp[i], dp[j - 2] * (i - j) + dp[j - 2]);
            }
        }

        return dp[n];
    }

    public static int keyBoard2(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1; //按A键

            for (int j = 4; j <= i; j++) {
                //dp[j - 3]为C-A之前的A个数，dp[j - 3] * (i - j + 1)为复制了(i - j + 1)
                dp[i] = Math.max(dp[i], dp[j - 3] * (i - j + 1) + dp[j - 3]);
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(keyBoard(1));
        System.out.println(keyBoard(2));
        System.out.println(keyBoard(3));
        System.out.println(keyBoard(5));
        System.out.println(keyBoard(6));
        System.out.println(keyBoard(7));
        System.out.println(keyBoard(9));

        System.out.println();
        System.out.println(keyBoard2(1));
        System.out.println(keyBoard2(2));
        System.out.println(keyBoard2(3));
        System.out.println(keyBoard2(5));
        System.out.println(keyBoard2(6));
        System.out.println(keyBoard2(7));
        System.out.println(keyBoard2(9));
    }
}
